//字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。 
//
// 
//
// 示例 1: 
//
// 输入: 
//first = "pale"
//second = "ple"
//输出: True 
//
// 
//
// 示例 2: 
//
// 输入: 
//first = "pales"
//second = "pal"
//输出: False
// 
// Related Topics 双指针 字符串 👍 206 👎 0

package com.cute.leetcode.editor.cn;
public class OneAwayLcci {
    public static void main(String[] args) {
        Solution solution = new OneAwayLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 编辑距离的问题
        public boolean oneEditAway(String first, String second) {
            int[][] dp = new int[first.length() + 1][second.length() + 1];
            // 初始化
            for (int i = 1; i <= first.length(); i++) dp[i][0] = i;
            for (int i = 1; i <= second.length(); i++) dp[0][i] = i;
            for (int i = 1; i <= first.length(); i++) {
                for (int j = 1; j <= second.length(); j++) {
                    // 当前字符相等，直接等于前一个位置
                    if (first.charAt(i - 1) == second.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                    else {
                        // first删除一个字符
                        int delete = dp[i - 1][j] + 1;
                        // first插入一个字符
                        int insert = dp[i][j - 1] + 1;
                        // first替换一个字符
                        int replace = dp[i - 1][j - 1] + 1;
                        dp[i][j] = Math.min(delete, Math.min(replace, insert));
                    }
                }
            }
            return dp[first.length()][second.length()] <= 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}